﻿// 0922train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色
 输出有多少种不同的染色方案？

输入描述
第一行输入M(图中节点数) N(边数)
后续N行格式为：V1 V2表示一个V1到V2的边
数据范围：1 <= M <= 15, 0 <= N <= M * 3，不能保证所有节点都是连通的

输出描述
输出一个数字表示染色方案的个数

输入
4 4
1 2
2 4
3 4
1 3
输出
7

4个节点，4条边，1号节点和2号节点相连，
2号节点和4号节点相连，3号节点和4号节点相连，
1号节点和3号节点相连，
若想必须保证相邻两个节点不能同时为红色，总共7种方案
 */
class Solution01
{
public:
    bool checkVerify(int index, vector<bool>& color_v)
    {
        if (neighbor_map.count(index) == 0) return true;

        for (auto&node:neighbor_map[index])
        {
            //邻接节点已经被染色
            if (color_v[node]) return false;
        }
        return true;
        //checkVerify
    }

    void backTrack(int start, vector<bool>&color_v)
    {
        for (auto& node : track_v)
        {
            if (!checkVerify(node, color_v))
                return;
        }
        result.push_back(track_v);

        if (start>total_)
        {
            return;
        }

        for (int i = start; i <= total_; i++)
        {
            color_v[i] = true;
            track_v.push_back(i);
            backTrack(i + 1, color_v);
            color_v[i] = false;
            track_v.pop_back();
            //for---
        }
        
        //backTrack
    }
    Solution01(vector<vector<int>>&num_vec, int total)
    {
        total_ = total;
        for (auto&item_v:num_vec)
        {
            int node_0 = item_v[0], node_1 = item_v[1];
            neighbor_map[node_0].push_back(node_1);
            neighbor_map[node_1].push_back(node_0);
        }

        vector<bool>color_v(total+1);

        for (int i=1; i<=total; i++)
        {
            color_v[i] = true;
            track_v.push_back(i);
            backTrack(i+1, color_v);
            color_v[i] = false;
            track_v.pop_back();
        }

        cout << result.size() + 1;
	    //Solution01
    }
private:
    int total_ = 0;
    vector<int>track_v;
    vector<vector<int>>result;
    unordered_map<int, vector<int>>neighbor_map;
};

/*
有N条线段，长度分别为a[1]-a[n]。
现要求你计算这N条线段最多可以组合成几个直角三角形
每条线段只能使用一次，每个三角形包含三条线段

输入描述
第一行输入一个正整数T（1<＝T<＝100），表示有T组测试数据
对于每组测试数据，接下来有T行，每行第一个正整数N，表示线段个数（3 <= N <= 20）
接着是N个正整数，表示每条线段长度，（0 < a[i] < 100）

输出描述
对于每组测试数据输出一行，每行包括一个整数，表示最多能组合的直角三角形个数

输入
1
7 3 4 5 6 5 12 13
输出
2

2
7 3 4 5 6 5 12 13
7 3 4 5 6 5 12 13
 */
class Solution02
{
public:
    void dfs(vector<int>& lines, int start, int count)
    {
        layer_result = max(layer_result, count);

        int lines_size = lines.size();
        for (int a = start; a < lines_size - 2; a++)
        {
            int a_line = lines[a];
            if (a_line == 0) continue;
            for (int b = a + 1; b < lines_size - 1; b++)
            {
                int b_line = lines[b];
                if (b_line == 0) continue;
                for (int c = b+1; c < lines_size; c++)
                {
                    int c_line = lines[c];
                    if (c_line == 0) continue;
                    if (a_line * a_line + b_line * b_line == c_line * c_line)
                    {
                        lines[a] = 0;
                        lines[b] = 0;
                        lines[c] = 0;
                        dfs(lines, a + 1, count+1);
                        lines[a] = a_line;
                        lines[b] = b_line;
                        lines[c] = c_line;
                    }
                }

                //for
            }
            //for
        }

	    //dfs
    }
    Solution02(vector<vector<int>>&total_lines)
    {
        for (auto&lines:total_lines)
        {
            sort(lines.begin(), lines.end());

            layer_result = 0;
            int lines_size = lines.size();
            dfs(lines, 0, 0);

            result.push_back(layer_result);
        }

        int result_size = result.size();
        for (int i=0; i< result_size; i++)
        {
            cout << result[i];
            if (i!=result_size-1)
            {
                cout << '\n';
            }
        }
	   //Solution02 
    }
private:
    int layer_result = 0;
    vector<int>result;
};

int main()
{
	{
        int row_size;
        cin >> row_size;

        vector<vector<int>>total_lines(row_size);
        for (int r=0; r< row_size; r++)
        {
            int col_size;
            cin >> col_size;
            vector<int>item_v(col_size);
            for (int c=0; c<col_size; c++)
            {
                cin >> item_v[c];
            }
            total_lines[r] = item_v;
        }

        Solution02 solu(total_lines);

        return 0;
	}
    //M(图中节点数) N(边数)
    int total, v_size;
    cin >> total >> v_size;

    vector<vector<int>>num_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        vector<int>item(2);
        cin >> item[0] >> item[1];
        num_vec[i] = item;
    }

    Solution01 solu(num_vec, total);


    //main
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
